package codingforgreat.class40;


import java.util.HashMap;

// 腾讯
// 分裂问题
// 一个数n，可以分裂成一个数组[n/2, n%2, n/2]
// 这个数组中哪个数不是1或者0，就继续分裂下去
// 比如 n = 5，一开始分裂成[2, 1, 2]
// [2, 1, 2]这个数组中不是1或者0的数，会继续分裂下去，比如两个2就继续分裂
// [2, 1, 2] -> [1, 0, 1, 1, 1, 0, 1]
// 那么我们说，5最后分裂成[1, 0, 1, 1, 1, 0, 1]
// 每一个数都可以这么分裂，在最终分裂的数组中，假设下标从1开始
// 给定三个数n、l、r，返回n的最终分裂数组里[l,r]范围上有几个1
// n <= 2 ^ 50，n是long类型
// r - l <= 50000，l和r是int类型
// 我们的课加个码:
// n是long类型随意多大都行
// l和r也是long类型随意多大都行，但要保证l<=r
public class Class01_SplitTo01 {
        public static long nums1(long n,long l,long r){
            if(n == 1 || n == 0){
                return n;
            }
            long half = size(n / 2);
            long left = l > half ? 0 : nums1(n / 2, l, Math.min(half, r));
            long mid = (l > half + 1 || r < half + 1) ? 0 : (n & 1);
            long right = r > half + 1 ? nums1(n / 2, Math.max(l - half - 1, 1), r - half - 1) : 0;
            return left + mid + right;

        }
        public static long size(long n){
            if(n == 0 || n == 1){
                return 1;
            }
            long half = size(n/2);
            return (half << 1) + 1;
        }


    public static long nums2(long n, long l, long r) {
        HashMap<Long, Long> allMap = new HashMap<>();
        return dp(n, l, r, allMap);
    }

    public static long dp(long n, long l, long r, HashMap<Long, Long> allMap) {
        if (n == 1 || n == 0) {
            return n == 1 ? 1 : 0;
        }
        long half = size(n / 2);
        long all = (half << 1) + 1;
        long mid = n & 1;
        if (l == 1 && r >= all) {
            if (allMap.containsKey(n)) {
                return allMap.get(n);
            } else {
                long count = dp(n / 2, 1, half, allMap);
                long ans = (count << 1) + mid;
                allMap.put(n, ans);
                return ans;
            }
        } else {
            mid = (l > half + 1 || r < half + 1) ? 0 : mid;
            long left = l > half ? 0 : dp(n / 2, l, Math.min(half, r), allMap);
            long right = r > half + 1 ? dp(n / 2, Math.max(l - half - 1, 1), r - half - 1, allMap) : 0;
            return left + mid + right;
        }
    }
}
